package LeetCode.leetcode;

import java.util.Arrays;

/**
 * @author: leiwenkang
 * @date: 2020/6/27
 * @time: 12:59
 */
public class Test204计数质数 {
    public static void main(String[] args) {
        System.out.println(countPrimes(10));
    }

    public static int countPrimes(int n) {
        boolean[] isPrim = new boolean[n];
        Arrays.fill(isPrim, true);

        for (int i = 2; i * i < n; i++) {
            if (isPrim[i]) {
                for (int j = i * i; j < n; j += i) {
                    isPrim[j] = false;
                }
            }
        }

        int count = 0;
        for (int i = 2; i < isPrim.length; i++) {
            if (isPrim[i]) {
                count++;
            }
        }

        return count;
    }

}
